package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 338. 比特位计数
 * @date 2025/2/24 10:54
 */
public class E338 {

    /**
     * <h3>方法一：位运算</h3>
     *
     * @param n 数字
     * @return 比特位计数数组
     */
    public int[] countBits1(int n) {
        int[] result = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            result[i] = countBit(i);
        }
        return result;
    }

    /**
     * 计算一个数字的1的比特位数
     *
     * @param num 数字
     * @return 比特位计数
     */
    private int countBit(int num) {
        int count = 0;
        while (num > 0) {
            count++;
            num &= (num - 1);
        }
        return count;
    }

    /**
     * <h3>方法二：动态规划</h3>
     *
     * @param n 数字
     * @return 比特位计数数组
     */
    public int[] countBits2(int n) {
        int[] result = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            // 假设n位，先统计前面n - 1位，最后统计最后一位
            result[i] = result[i >> 1] + (i & 1);
        }
        return result;
    }

    /**
     * <h3>方法三：用Integer类的bitCount方法</h3>
     *
     * @param n 数字
     * @return 比特位计数数组
     */
    public int[] countBits3(int n) {
        int[] result = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            result[i] = Integer.bitCount(i);
        }
        return result;
    }
}
